local function heapsort(a)
  local n = #a
  local j, i, t
  local l = math.floor(n / 2) + 1
  local k = n
  while true do
    if l > 1 then
      l = l - 1
      t = a[l]
    else
      t = a[k]
      a[k] = a[1]
      k = k - 1
      if k == 1 then
        a[1] = t
        return
      end
    end
    i = l
    j = l * 2
    while j <= k do
      if j < k and a[j] < a[j+1] then
        j = j + 1
      end
      if t < a[j] then
        a[i] = a[j]
        i = j
        j = j + i
      else
        j = k + 1
      end
    end
    a[i] = t
  end
end

local function random_int(seed)
  return (214013 * seed + 2531011) % 2147483648
end

local N = 1000000
local a = {}
local rand = 123456789
for i=1,N do
  rand = random_int(rand)
  a[i] = rand
end

heapsort(a)

local sum = 0.0
for i=1,N-1 do
  assert(a[i] <= a[i+1])
  sum = sum + (a[i+1] - a[i])
end
print(sum)
assert(sum == 2147480127.0)
